/**
 * 插入区间
 *
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
 * 在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
 * 返回插入之后的 intervals。
 * 注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
 *
 * 示例 1：
 * 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 * 输出：[[1,5],[6,9]]
 *
 * 示例 2：
 * 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * 输出：[[1,2],[3,10],[12,16]]
 * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 *
 * 提示：
 * 0 <= intervals.length <= 104
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 105
 * intervals 根据 starti 按 升序 排列
 * newInterval.length == 2
 * 0 <= start <= end <= 105
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 这里给了我们一个数组, 让我们插入原来的有序数组中, 可以知道, 这个数组
 * 和原数组中的每一个数相比的话, 有三种可能性
 * 1. 在原数组左边   我们之歌时候可以将数组插入, 但是因为已经循环了一次, 我们
 * 需要将原来这个位置的数组再次进行插入
 * 2. 在原数组右边   这个就可以将原数组进行插入
 * 3. 和原数组有交集  这里我们需要更新一下需要插入数组的区间, 因为我们不知道后面还会不会
 * 有区间也是需要合并的, 所以我们只更新下区间就可以了, 不用着急将它加入 list
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public int[][] insert(int[][] intervals, int[] newInterval) {

        // 创建列表
        List<int[]> list = new ArrayList<>();

        // 数组列数
        int n = intervals.length;

        // 这里我们将需要插入的数组中的元素定义出来, 后面反复用到
        int c = newInterval[0], d = newInterval[1];

        // 注意我们要设置一个全局变量, 为了看 需要插入的数组是否已经插入
        // 要是中间已经插入的话, 就没有必要再进行插入了
        // 要是到结尾都没有插入的话, 就在最后插入
        boolean tmp = false;

        // 遍历原数组
        for (int i = 0; i < n; i++) {

            // 这里也提前将数组的这个位置的值定义出来
            int a = intervals[i][0], b = intervals[i][1];

            if (d < a) {

                // 要插入的数组在这个位置的左边

                // 我们先判断下是否已经插入过了
                if (!tmp) {

                    // 没有插入, 插入
                    list.add(new int[]{c, d});

                    // 该标记
                    tmp = true;
                }

                // 不要忘记插入原来的数组
                // 不然这个位置就会被省略
                list.add(new int[]{a, b});

            } else if (c > b) {

                // 在这个位置的右边, 插入原数组
                list.add(new int[]{a, b});
            } else {

                // 这里有交集

                // 求交集的最小边界
                // 注意 可不敢直接写 a, 我们看上去好像是 a
                // 最小, 实际上, 只有一开始的时候, a 是最小的
                // 往后面遍历的时候, 我们确实 此时 c 是上次的 a 最小的
                // 但是因为 这次的 a 会变, c 继续 = a 就出错了, 所以要
                // 取他们的最小
                c = Math.min(a, c);

                // 右边界取最大
                d = Math.max(b, d);
            }
        }

        // 要是到结尾了还是没有插入要插入的数组, 插入数组
        if (!tmp) {
            list.add(new int[]{c, d});
        }

        // 将 list 转化为 二维数组
        return list.toArray(new int[list.size()][]);
    }
}